Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Find Pivot Index

Problem Statement

Given an integer array nums, determine the pivot index of this array.

The pivot index divides the array in such a way that the sum of the numbers on its left side is exactly equal to the sum of the numbers on its right side.

If the index is at the beginning, the sum to its left is considered zero, similarly for an index at the end.

Return the leftmost pivot index. If no such index exists, return -1.

Examples

  • Example 1:

    • Input: [1, 2, 3, 4, 3, 2, 1]
    • Expected Output: 3
    • Justification: The sum of the numbers to the left of index 3 (1 + 2 + 3) is 6, and the sum to its right (3 + 2 + 1) is also 6.
  • Example 2:

    • Input: [2, 1, 3]
    • Expected Output: -1
    • Justification: There is no pivot index that exists in the given array.
  • Example 3:

    • Input: [1, 100, 50, -51, 1, 1]
    • Expected Output: 1
    • Justification: The sum to the left of index 1 is 1, and the sum to its right (50 + (-51) + 1 + 1) is 1.

Solution

To solve this problem, we'll employ a two-step approach to ensure efficiency and simplicity. Initially, we calculate the total sum of all array elements. Knowing the total, we can iterate through the array, maintaining a running sum of elements to the left of the current index. At any point, if the left sum is equal to the total minus the left sum minus the current element, we've found our pivot index. This method is effective because it only requires a single pass through the array after calculating the total sum, making it efficient in terms of both time and space.

The reason this approach is particularly appealing is its simplicity and the fact that it leverages the arithmetic property of sums. This allows for quick determination of the pivot index without needing complex data structures or multiple passes through the array, making it an ideal choice for this problem.

Step-by-step algorithm:

  • Calculate the total sum of the array elements.
  • Initialize a variable to keep track of the sum of elements to the left of the current index (leftSum) and set it to 0.
  • Iterate through the array:
    • At each index, check if leftSum is equal to the total sum minus leftSum minus the current element. If true, return the current index as the pivot index.
    • Otherwise, add the current element to leftSum and continue.
  • If no pivot index is found during the iteration, return -1.

Algorithm Walkthrough

Using the input [1, 2, 3, 4, 3, 2, 1]:

Step 1: Calculate the Total Sum of the Array

  1. Initialize the totalSum variable to 0.
  2. Add each element in the array to totalSum:
    • After adding 1, totalSum is 1.
    • After adding 2, totalSum is 3.
    • After adding 3, totalSum is 6.
    • After adding 4, totalSum is 10.
    • After adding the second 3, totalSum is 13.
    • After adding the second 2, totalSum is 15.
    • After adding the second 1, totalSum is 16.

Step 2: Iterate Through the Array to Find the Pivot Index

  1. Initialize the leftSum variable to 0.
  2. Iterate through the array, calculating the leftSum and comparing it with the sum of elements to the right of the current index to find the pivot index.

Iteration 1: Index 0 ([1])

  • leftSum is 0.
  • The sum to the right is totalSum - leftSum - nums[i] = 16 - 0 - 1 = 15.
  • The sums are not equal, so continue.

Iteration 2: Index 1 ([1, 2])

  • Update leftSum to 1 (0 + 1).
  • The sum to the right is totalSum - leftSum - nums[i] = 16 - 1 - 2 = 13.
  • The sums are not equal, so continue.

Iteration 3: Index 2 ([1, 2, 3])

  • Update leftSum to 3 (1 + 2).
  • The sum to the right is totalSum - leftSum - nums[i] = 16 - 3 - 3 = 10.
  • The sums are not equal, so continue.

Iteration 4: Index 3 ([1, 2, 3, 4])

  • Update leftSum to 6 (3 + 3).
  • The sum to the right is totalSum - leftSum - nums[i] = 16 - 6 - 4 = 6.
  • The sums are equal, which means we've found the pivot index at 3.

Final Result:

The pivot index for the array [1, 2, 3, 4, 3, 2, 1] is 3, as the sum of the numbers to the left of index 3 is equal to the sum of the numbers to its right, both summing to 6.

Image

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity for the algorithm is , where (n) is the number of elements in the input array. This efficiency is due to the algorithm requiring a single pass to calculate the total sum and another pass to find the pivot index, making the operations linear in time relative to the size of the input.

Space Complexity

The space complexity of the algorithm is . This is because the amount of extra space required does not scale with the size of the input array.

Find Pivot Index (easy)
Isomorphic Strings (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step algorithm:

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity